Allows to create a Look-Up-Table (LUT) of a Huffman tree. More...
Public Member Functions | |
HuffmanLut (const HuffmanTreeDescriptor &descriptor) | |
~HuffmanLut () | |
HuffmanSymbol | get (unsigned int input) |
unsigned int | getLutSize () const |
unsigned int | getMaxSymbolSize () const |
Allows to create a Look-Up-Table (LUT) of a Huffman tree.
A Huffman tree allows to compress data at the bits level, by creating a dictionary that will translate a certain pattern of bits, into another, often smaller. It is often represented as a binary tree, with each code's 0 and 1 encoding left or right until getting to a symbol at the designated leaf. However, traversing the tree everytime is not ideal for performance reasons. This LUT aims to flatten the lookup time into a simple indexing operation.
However, this comes with some constraints :
For instance, if the tree features codes with 7 bits and at most 9 bits, then a code such as 0b1100011 should be padded to become 0b110001100 before looking up.
A typical usage is to use a BitStream as such :
... nkMemory::HuffmanLut lut (...) ; nkMemory::BitStream stream (data) ; nkMemory::HuffmanSymbol lookup = lut.get(stream.peekMsb(lut.getMaxSymbolSize())) ; stream.moveForward(lookup._size) ; // Use lookup._value as needed ...
nkMemory::HuffmanLut::HuffmanLut | ( | const HuffmanTreeDescriptor & | descriptor | ) |
Constructor. The descriptor data is interpreted sequentially. As such :
As an example, a simple tree can be created with :
nkMemory::HuffmanTreeDescriptor descriptor ; descriptor._perBitsCounts[0] = 1 ; descriptor._perBitsCounts[1] = 2 ; descriptor._table = {128u, 12u, 13u} ;
This tree will feature 3 symbols, the first with a code of size 1, and the 2 next of size 2. More precisely : 128 (encoded by 0), 12 (encoded by 10), and 13 (encoded by 11).
descriptor | The tree descriptor to use for the tree, and ultimately LUT creation. |
nkMemory::HuffmanLut::~HuffmanLut | ( | ) |
Destructor.
HuffmanSymbol nkMemory::HuffmanLut::get | ( | unsigned int | input | ) |
input | The input binary code to lookup for. |
unsigned int nkMemory::HuffmanLut::getLutSize | ( | ) | const |
unsigned int nkMemory::HuffmanLut::getMaxSymbolSize | ( | ) | const |